/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/6
 * \* Time: 10:32
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 不同的二叉搜索树 {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i < n + 1; i++){
            for(int j = 1; j < i + 1; j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
    //下面的方法超时
//    /**
//     * 主函数
//     * @param n
//     * @return
//     */
//    int numTrees(int n) {
//        // 计算闭区间 [1, n] 组成的 BST 个数
//        return count(1, n);
//    }
//
//    /**
//     * 计算闭区间 [lo, hi] 组成的 BST 个数
//     * @param lo
//     * @param hi
//     * @return
//     */
//    int count(int lo, int hi) {
//        // base case
//        if (lo > hi) {
//            return 1;
//        }
//        int res = 0;
//        for (int i = lo; i <= hi; i++) {
//            // i 的值作为根节点 root
//            int left = count(lo, i - 1);
//            int right = count(i + 1, hi);
//            // 左右子树的组合数乘积是 BST 的总数
//            res += left * right;
//        }
//        return res;
//    }
}